package medium;

import java.util.HashMap;
/*
105. 从前序与中序遍历序列构造二叉树
 */
public class LeeCode105 {

  public static void main(String[] args) {

  }


  public TreeNode buildTree(int[] preorder, int[] inorder) {

    int preLength = preorder.length;
    int inLength = inorder.length;
//用来存放中序遍历的节点，以便快速定位到节点下标
    HashMap<Integer, Integer>map = new HashMap<>(preLength);
    for (int i = 0; i < inLength; i++) {
      map.put(inorder[i],i);
    }

    return myBuildTree(preorder,inorder,0,preLength - 1,0,inLength - 1,map);
  }

  /*
  preLeft:前序遍历子区间的左边界
  preRight:前序遍历子区间的右边界
  inLeft:中序遍历子区间的左边界
  inRight:中序遍历子区间的右边界
   */
  public TreeNode myBuildTree(int[] preorder, int[] inorder, int preLeft, int preRight, int inLeft, int inRight,HashMap<Integer,Integer>map){
    if (preLeft > preRight){
      return null;
    }

    int rootVal = preorder[preLeft];

    TreeNode root = new TreeNode(rootVal);

    int pIndex = map.get(rootVal);

    root.left = myBuildTree(preorder,inorder,preLeft + 1,pIndex - inLeft + preLeft,inLeft,pIndex - 1,map);
    root.right = myBuildTree(preorder,inorder,pIndex - inLeft + preLeft + 1,preRight,pIndex + 1,inRight,map);

    return root;
  }


   public class TreeNode {
     int val;
     TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
}
